class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        if m > n:
            m, n = n, m

        left, right = 1, m * n
        while left < right:
            mid = (left + right) // 2

            res = 0
            for i in range(1, m + 1):
                res += min(mid // i, n)

            # 小于等于mid的数字超过k个 -> mid过大
            if res > k :
                right = mid

            # 小于等于mid的数字少于k个 -> mid过小
            elif res < k :
                left = mid + 1

            # 小于等于mid的数字正好为k个 -> mid可能还可以更小
            else:
                right = mid

        return left


if __name__ == "__main__":
    print(Solution().findKthNumber(3, 3, 5))  # 3
    print(Solution().findKthNumber(2, 3, 6))  # 6
